1、数组出现超过一半的数
思想：将数组中数放到map中，因为map有统计计数功能，在遍历一下，找出计数结果大于size/2的
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> m;
        for(auto e:nums)
        {
            m[e]++;
        }
        for(auto e:m)
        {
            if(e.second>((nums.size())/2))
            {
                return e.first;
            }
        }
        return -1;
    }
};

2、数据流中的中位数，如果size为奇数，就是中间数，如果size为偶数，就是中间两数加起来相除
思想：建立2个堆，一个为大堆，用来存储小的数，一个为小堆，用来存储大数；
          优先让大堆先进数据，但是得确保大堆小堆的个数差不能大于1，因为我们得确保中间数在堆顶，
          也就是如果size为偶数，2个堆数得个数相等，那么2个堆顶就是中间数，如果size为奇数，那么
          size大的堆的堆顶元素就是中间数
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int,vector<int>,greater<int>> big;
    priority_queue<int> small;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(small.empty()==true)
        {
            small.push(num);
            return;
        }
        if(num>small.top())
        {
            big.push(num);
        }
        else
        {
            small.push(num);
        }
        if(small.size()-big.size()==2)
        {
            big.push(small.top());
            small.pop();
        }
        if(big.size()-small.size()==2)
        {
            small.push(big.top());
            big.pop();
        }

    }
    
    double findMedian() {
        if(small.size()!=big.size())
        {
            return small.size()>big.size()?(double)small.top():(double)big.top();
        }
        else
        {
            double x1=(double)(small.top());
            double x2=(double)(big.top());
            return (x1+x2)/2;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

3、递增的数组中找个数和为s
思想：双指针法，left+right   如果大于s  right--，  如果小于s，  left++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        int left=0;
        int right=nums.size()-1;
        while(left<right&&(nums[left]+nums[right])!=target)
        {
            while(left<right&&(nums[left]+nums[right])<target)
            {
                left++;
            }
            while(left<right&&(nums[left]+nums[right])>target)
            {
                right--;
            }
        }
        v.push_back(nums[left]);
        v.push_back(nums[right]);
        return v;
    }
};
